public class Code1 {
    // 摆动序列

    public int wiggleMaxLength(int[] nums) {
        // 创建 dp 表
        // 初始化
        // 填表
        // 返回值

        // 我们先分析题目，可以先有一个创建 dp 表的思路
        // dp[i] 表示的是，以 i 元素为结尾的所有子序列中，最长摆动序列的长度
        // 但是 摆动序列 也就是说其中的数据是存在上下起伏的，所以，在上面的 dp 中只是单独获取最长摆动序列的长度，其实是可以在进行细分
        // 设置 f[i] 表示的是，以 i 位置为结尾的所有子序列中，与 i - 1 位置的元素构成上升趋势的，最长摆动长度
        // 设置 g[i] 表示的是，以 i 位置为结尾的所有子序列中，与 i - 1 位置的元素构成下降趋势的，最长摆动长度
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];

        // 进行初始化操作
        // 通过题目我们可以知道 当只有 1 个元素的时候，其自身就可以作为摆动序列的一个长度，所以我们可以将 f g 表中的元素全部初始化为 1
        for(int i = 0; i < n; i++){
            f[i] = g[i] = 1;
        }

        // 进行填表操作，这里的填表是从左向右填写，并且是两个表同时进行
        // 对于表的填写，我们可以将其划分为两部分
        // 第一部分，即就是当前元素自身作为一个最大子序列，即为 1
        // 第二部分，即就是 i 之前的元素，在符合条件的情况下与 i 一并组成最长子序列，这里设定 i 之前的元素（i - 1，i - 2... 0）为 j
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                // 针对 f 表 (上升状态下的最长元素)
                if(nums[j] < nums[i]){
                    // 为了获取到最大长度，这里需要将，下降位置 + 1 与当前的情况进行比较来得到最大值
                    f[i] = Math.max(g[j] + 1, f[i]);
                }else if(nums[j] > nums[i]){
                    g[i] = Math.max(f[j] + 1, g[i]);
                }
            }
        }
        // 确定返回值
        // 这里的返回值是需要获取到 f ，g 表中的最大值
        int ret = 0;
        for(int s = 0; s < n; s++){
            ret = Math.max(ret, Math.max(f[s], g[s]));
        }
        return ret;
    }
}
